#include "stdio.h"
#include "string.h"
#include "stdlib.h"
char NT[10][10];        //non-terminal
char T[20][10];         //terminal
char table[20][10][20]; //predict table
/*
    E->TA
    A->+TA|e
    T->FB
    B->*FB|e
    F->(E)|id
    step 1:
    create first,follow;
    how to store production     
    follow(E) = {$,)}
    follow(A) = {$}
    follow(T) = {+,$}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
    follow(B) = {+,$}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
    follow(F) = {*,+,$}   

    follow(E) = {$,)}
    follow(A) = {$}
    follow(T) = {+,$,}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
    follow(B) = {+,$,}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
    follow(F) = {*,+,$,}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
*/
struct Notation
{
    char name[10];
    int n, firstN, followN;
    struct Node *p[20]; // production
    char first[20][10];
    char follow[20][10];
} Notation;
struct Node
{
    char name[10];
    int hase;
    struct Node *next;
} Node;
/*
scan the string
init notation's name when get "->"
create production Node and link them all until get '|'.
j++ when get '|' working pointer to p[j]
*/
struct Notation init(char production[], int length)
{
    int n, j = 0, i = 0;
    char name[10] = {""};
    struct Notation notation;
    struct Node *p[10];
    struct Node *w = NULL;
    struct Node *temp = NULL;
    //init notation
    while (production[i] != '-')
    {
        ++i;
    }
    if (production[i + 1] != '>')
    {
        printf("error!");
        exit(0);
    }
    else
    {
        strncpy(name, production, i);
        name[i] = '\0';
        strcpy(notation.name, name);
    }

    for (i = i + 2; i < length; i++)
    {
        // non-terminal init
        if (production[i] >= 'A' && production[i] <= 'Z')
        {
            temp = (struct Node *)malloc(sizeof(struct Node));
            temp->next = NULL;
            if (production[i + 1] == '\'')
            {
                name[0] = production[i++];
                name[1] = production[i];
                name[2] = '\0';
            }
            else
            {
                name[0] = production[i];
                name[1] = '\0';
            }

            strcpy(temp->name, name);
            //when w == NULL, make w point to current location and the first node of production
            //of current notation is temp, else link current node and point to it
            if (w != NULL)
            {
                w->next = temp;
                w = w->next;
            }
            else
            {
                w = temp;
                notation.p[j++] = w;
            }
        }
        //terminal init
        else if (production[i] != '|')
        {
            temp = (struct Node *)malloc(sizeof(struct Node));
            temp->next = NULL;

            if (production[i] == '+' || production[i] == '*' || production[i] == '(' || production[i] == ')')
            {
                name[0] = production[i];
                name[1] = '\0';
            }
            else if (production[i] == 'i' && production[i + 1] == 'd')
            {
                name[0] = production[i++];
                name[1] = production[i];
                name[2] = '\0';
            }
            else if (production[i] == 'e')
            {
                name[0] = production[i];
                name[1] = '\0';
                temp->hase = 1;
            }
            strcpy(temp->name, name);
            //when w == NULL, make w point to current location and the first node of production
            //of current notation is temp, else link current node and point to it
            if (w != NULL)
            {
                w->next = temp;
                w = w->next;
            }
            else
            {
                w = temp;
                notation.p[j++] = w;
            }
        }
        else if (production[i] == '|')
        {
            w = NULL;
        }
    }
    notation.n = j;
    return notation;
}
/*
    scan production with the rule of creating fisrt until nothing change in each first 
    cycle 1:
    first(E) = {}
    first(E') = {+,e}
    first(T) = {}
    first(T') = {*,e}
    first(F) = {(,id}
    
    cycle 2:
    first(E) = {}
    first(E') = {+,e}
    first(T) = {(,id}
    first(T') = {*,e}
    first(F) = {(,id}

    cycle 3:
    first(E) = {(,id}
    first(E') = {+,e}
    first(T) = {(,id}
    first(T') = {*,e}
    first(F) = {(,id}
*/
void fisrt(struct Notation ns[], int n)
{
    int flag = 1, firstN;
    int i,j,k;
    struct Notation *no;
    struct Node *t;
    while (flag)
    {
        flag = 0;
        //get i th production
        for (i = 0; i < n; i++)
        {
            no = ns + i;
            no->firstN = 0;
            //san p i th production
            for (j = 0; j < no->n; j++)
            {
                t = no->p[j];
                while (t != NULL)
                {
                    // deal with terminal 
                    if (t->name[0] == '+' || t->name[0] == '*' || t->name[0] == '(' || t->name[0] == ')' || t->name[0] == 'e' || strcmp(t->name, "id"))
                    {
                        // notInFirst()
                        strcpy(no->first[no->firstN++], t->name);
                        flag = 1;
                        break;
                    }
                    // deal with non-terminal
                    else
                    {
                        /*
                            E->AB
                            state 1:add first(A)
                            s1: find A when create first
                            read the node's name
                            find from the notations O(n2)
                            get its first
                            state 2:if A->e, add first(B) by state1
                        */
                       for(k = 0;k < n; ++ k)
                       {
                           if(strcmp(ns[k].name,t->name))
                           {
                               if(ns[k].firstN != 0)
                               {

                               }
                           }
                       }
                    }
                }
            }
        }
    }
}
int main()
{
    char production[5][20] = {"E->TE'", "E'->+TE'|e", "T->FT'", "T'->*FT'|e", "F->(E)|id"};
    struct Notation ns[5];
    // struct Notation E = init(production, sizeof(production) - 1);
    // printf("%s %d\n", E.name, E.n);
    // struct Node *t;
    for (int i = 0; i < 5; i++)
    {
        ns[i] = init(production[i], sizeof(production[i]) - 1);
        printf("%s\n", ns[i].name);
    }
    return 0;
}